\documentclass{beamer}
\usepackage[UTF8]{ctex}
\usepackage{latexsym,amssymb,amsmath,amsbsy,amsopn,amstext,xcolor,multicol}
\usepackage{graphicx,wrapfig,fancybox}
\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
\usepackage{booktabs} 
\usepackage{listings}
\usepackage{xcolor}  % 用到了 \color 命令
\usetheme{thubeamer} % 使用thu主题

\title{差分数组}

\author[wym510]{伍一鸣}

% \institute{所属机构}

\date{}

% \date{\today}  % 使用当前日期

\begin{document}
\setbeamertemplate{transition page}{Cover}
% 标题页幻灯片
	
\maketitle

% 正文幻灯片

\begin{frame}{复习}
\begin{definition}
	前缀和数组$Sum$
	
	\begin{itemize}
		\item $Sum_i = A_1+A_2+A_3+\dots+A_i$
	\end{itemize}
\end{definition}
\begin{Corollary}
	\begin{itemize}
		\item $Sum_i = Sum_{i-1}+A_i$
		\item $A_l+A_{l+1}+A_{l+2}+\cdots+A_{r-1}+A_r = Sum_r-Sum_{l-1}$
	\end{itemize}
\end{Corollary}
	前缀和这一工具使得我们能够解决快速查询区间内元素的和这一类问题
\end{frame}
\begin{frame}[fragile]
	\frametitle{洛谷 - P2367}
	\begin{problem}
		给定一个包含 $n$个整数的数组$a$，一共$p$个操作。第$i$次操作把第$x_i$到第$y_i$个数字都加上$z_i$，求$p$次操作之后数组中最小的数。$n\leq 5*10^6,p\leq n$
	\end{problem}
	\pause
	\begin{solution}
		一个简单的想法：对每一个操作用for循环直接修改$a$数组
	\end{solution}
	\begin{lstlisting}
	for(int j = x[i]; j <= y[i]; j++) 
	  a[j] += z[i];
	\end{lstlisting}

\end{frame}

\begin{frame}{洛谷 - P2367}
	\begin{definition}
		差分数组$Diff$
	
		\begin{itemize}
			\item $Diff_i = A_i-A_{i-1}$，其中$A_0=A_{n+1}=0$
		\end{itemize}
	\end{definition}
	\pause
	\begin{Corollary}
		\begin{itemize}
			\item $A_i=A_{i-1}+Diff_i$
			\pause
			\item $Diff$数组和$A$数组一一对应， $Diff$数组可以确定唯一的$A$数组
			\pause
			\item $Diff_1+Diff_2+Diff_3+\cdots+Diff_{n+1}=0$
		\end{itemize}
	\end{Corollary}
\end{frame}

\begin{frame}{洛谷 - P2367}
	\begin{solution}
		\begin{itemize}
			\item 因为$Diff$数组和$A$数组一一对应，所以需要修改$A$数组时，可以用修改$Diff$数组代替
			\pause
			\item 考虑清楚$A$数组的变化在$Diff$数组中会引起怎样的变化
			\pause
			\item 把$A$数组第$x_i$到第$y_i$个数字都加上$z_i$，那么$Diff$数组只会有两个数字发生变化，即$Diff_{x_i},Diff_{y_i+1}$
			\pause
			\item 最后通过$A_i=A_{i-1}+Diff_i$还原出$A$数组取出最小值即可
		\end{itemize}
	\end{solution}
\end{frame}

\begin{frame}{CodeForces - 295A}
	\begin{problem}
		给定一个包含 $n$个整数的数组$A$，一共$m$个操作，$k$个查询。第$i$个操作把第$l_i$到第$r_i$个数字都加上$d_i$。第$i$次查询会把第$x_i$到第$y_i$个操作用在数组$a$上，求$k$个操作之后的数组$A$。
	\end{problem}
\end{frame}

\begin{frame}{CodeForces - 295A}
	\begin{solution}
		\begin{itemize}
			\item 难点在于每个操作在$k$次查询中被用到了多少次
			\pause
			\item 这个也可以用差分数组来求
			\pause
			\item 如果第$i$个操作被用到了$B_i$次，那么第$i$个操作把第$l_i$到第$r_i$个数字都加上$d_i*B_i$
		\end{itemize}
	\end{solution}
\end{frame}

\begin{frame}{洛谷 - P1969}
	\begin{problem}
		给定包含 $n$个整数的数组$H$和全 $n$个0的数组$B$，每次操作可以选定一对$l,r$，将$B_l,B_{l+1},...,B{r}$都加上1，问将$B$变成$H$最小的操作次数。
	\end{problem}
\end{frame}

\begin{frame}{洛谷 - P1969}
	\begin{solution}
		\begin{itemize}
			\item 每次对于$B$的操作会把$DiffB_{l}+1,DiffB_{r+1}-1$
			\pause
			\item 最后只要把$DiffB$和$DiffH$变成一样的即可
			\pause
			\item 因为$Diff_1+Diff_2+Diff_3+\cdots+Diff_{n+1}=0$，所以$DiffH$中所有正数的和就是最小的操作次数
		\end{itemize}
	\end{solution}
\end{frame}

\end{document}